package seqlist;

/**
 * @author shkstart
 * @create 2022-08-12-16:44
 */
public class SingleLinkedListWithHead {

    //虚拟头节点
    private Node dummyHead = new Node(-1);
    //    单链表中具体节点的个数（不包含虚拟头节点）
    private int size;

    /**
     * 此时可以在任意位置插入
     *
     * @param index
     * @param data
     */
    public void addIndex(int index, int data) {

        if (index < 0 || index > size) {
            System.err.println("index非法");
            return;
        }
//        一定存在前驱节点
        Node perv = dummyHead;
//        因为存在虚拟头节点，所以i比之前多走一次才到达待删除节点的前驱节点
        for (int i = 0; i < index; i++) {
            perv = perv.next;
        }
        //知道待插入节点的前驱节点
        Node node = new Node(data);
        node.next = perv.next;
        perv.next = node;
        size++;
    }

    public void addFirst(int data) {
        addIndex(0, data);
    }

    public void addLast(int data) {
        addIndex(size, data);
    }

    /**
     * 返回删除前的值
     * @param index
     */
    public int  removeIndex(int index){
        if (index < 0 || index >= size) {
            System.err.println("index不合法");
            return  -1;
        }
        Node perv = dummyHead;
        for (int i = 0; i < index; i++) {
            perv= perv.next;
        }
        Node node = perv.next;
        perv.next = node.next;
        int old = node.data;
        node.next=null;
        size--;
        return old;
    }
    public int removeFirst(){
        return removeIndex(0);
    }
    public int removeLast(){
        return removeIndex(size-1);
    }



    @Override
    public String toString() {
        String ret = "";
        Node node = dummyHead.next;
        while (node != null) {
            ret += node.data + "->";
            node = node.next;
        }
        ret += "null";
        return ret;
    }

    public static void main(String[] args) {

        SingleLinkedListWithHead withHead = new SingleLinkedListWithHead();
        withHead.addFirst(1);
        withHead.addLast(2);
        withHead.addLast(3);
        withHead.addIndex(1, 10);
        //1->10->2->3->null
        System.out.println(withHead);
        System.out.println(withHead.removeFirst());
        System.out.println(withHead.removeLast());
        //10->2->null
        System.out.println(withHead);
        System.out.println(withHead.removeIndex(0));
        System.out.println(withHead);
    }


}
